//给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。 
//
// 回文串 是正着读和反着读都一样的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aab"
//输出：[["a","a","b"],["aa","b"]]
// 
//
// 示例 2： 
//
// 
//输入：s = "a"
//输出：[["a"]]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 16 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 回溯 
// 👍 911 👎 0

package com.cute.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

public class PalindromePartitioning {
    public static void main(String[] args) {
        Solution solution = new PalindromePartitioning().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 是将字符串进行分割，不是找出所有的回文串
     * 要的是所有的分割方法：没有什么思路
     * 两个点：
     *  1.储存子串是否为回文串（可以使用dp来存储，也可以每次都进行双指针判断）
     *  2.子串的添加以及剪枝dfs回溯，只有当前缀是回文串的时候再进行下一步的遍历
     */
    class Solution {
        public List<List<String>> partition(String s) {
            int len = s.length();
            if (len == 0) return null;
            List<List<String>> res = new ArrayList<>();
            List<String> temp = new ArrayList<>();
            //处理字符串
            char[] charArray = s.toCharArray();
            //TODO 状态转移方程存储字符串s[i][j]是否为回文字符串
            // 使用DP判断回文串的方法最好是记下来
            boolean[][] dp = new boolean[len][len];
            for (int right = 0; right < len; right++) {
                //这里left=right是保证单个字符也能判断
                for (int left = 0; left <= right; left++) {
                    if (charArray[left] == charArray[right]&&(right-left<=2||dp[left+1][right-1]))
                        dp[left][right]=true;
                }
            }
            dfs(0,s,len,dp,temp,res);
            return res;

        }

        private void dfs(int begin, String s,int len, boolean[][] dp, List<String> temp, List<List<String>> res) {
            if (begin == len){
                res.add(new ArrayList<>(temp));
            }else {
                for (int i = begin; i < len ; i++) {
                    if (dp[begin][i]){//前缀字符串是回文串时才有必要向下进行
                        temp.add(s.substring(begin, i+1));
                        dfs(i+1, s, len, dp, temp, res);
                        temp.remove(temp.size()-1);
                    }
                }
            }
        }


        /**
         * 二刷的时候没想到用dp存储，用的这个方法判断字符串是否为回文串，用dp存储结果更快
         */
        public boolean helper(String s){//每次都这样遍历其实比较耗时，可以使用dp先做一次判断并存储结果就行了
            int i = 0;
            int j = s.length()-1;
            char[] chars = s.toCharArray();
            while (i<j){
                if(chars[i++]!=chars[j--]) return false;
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}